package org.nlp.algo.hash.ConsistencyHash;

import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;

import com.google.common.hash.Hashing;

/**
 * Created by IntelliJ IDEA. User: test Date: 12-5-24 Time: ����5:37 To change
 * this template use File | Settings | File Templates.
 */
public class ConsistencyHash {
	private TreeMap<Long, Object> nodes = null;
	// ��ʵ�������ڵ���Ϣ
	private List<Object> shards = new ArrayList<Object>();
	// ��������ڵ���Ŀ
	private int VIRTUAL_NUM = 1;

	public ConsistencyHash() {

	}

	public ConsistencyHash(int VIRTUAL_NUM) {
		if (VIRTUAL_NUM > 0)
			this.VIRTUAL_NUM = VIRTUAL_NUM;
	}

	/**
	 * ���key��hashֵȡ�÷������ڵ���Ϣ
	 * 
	 * @param hash
	 * @return
	 */
	public Object getShardInfo(long hash) {
		Long key = hash;
		SortedMap<Long, Object> tailMap = nodes.tailMap(key);
		if (tailMap.isEmpty()) {
			key = nodes.firstKey();
		} else {
			key = tailMap.firstKey();
		}
		return nodes.get(key);
	}

	/**
	 * ��ӡԲ���ڵ����
	 */
	public void printMap() {
		System.out.println(nodes);
		System.out.println(nodes.size());
	}

	/**
	 * ���2^32�ѽڵ�ֲ���Բ�����档
	 * 
	 * @param digest
	 * @param nTime
	 * @return
	 */
	public long hash(byte[] digest, int nTime) {
		long rv = ((long) (digest[3 + nTime * 4] & 0xFF) << 24)
				| ((long) (digest[2 + nTime * 4] & 0xFF) << 16)
				| ((long) (digest[1 + nTime * 4] & 0xFF) << 8)
				| (digest[0 + nTime * 4] & 0xFF);

		return rv & 0xffffffffL; /* Truncate to 32-bits */
	}

	/**
	 * Get the md5 of the given key. ����MD5ֵ
	 */
	public byte[] getHash(String k) {
		MessageDigest md5;
		try {
			md5 = MessageDigest.getInstance("MD5");
		} catch (NoSuchAlgorithmException e) {
			throw new RuntimeException("MD5 not supported", e);
		}
		md5.reset();
		byte[] keyBytes = null;
		try {
			keyBytes = k.getBytes("UTF-8");
		} catch (UnsupportedEncodingException e) {
			throw new RuntimeException("Unknown string :" + k, e);
		}

		md5.update(keyBytes);
		return md5.digest();
	}

	public static String toHexString(byte[] b) {
		char[] hexChar = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
				'a', 'b', 'c', 'd', 'e', 'f' };
		StringBuilder sb = new StringBuilder(b.length * 2);
		for (int i = 0; i < b.length; i++) {
			sb.append(hexChar[(b[i] & 0xf0) >>> 4]);
			sb.append(hexChar[b[i] & 0x0f]);
		}
		return sb.toString();
	}

	private void updateShardInfo() {
		// System.out.println("shards size:" + shards.size());
		nodes = new TreeMap<Long, Object>();
		for (int i = 0, len = shards.size(); i < len; i++) {
			Object shardInfo = shards.get(i);
			for (int j = 0; j < VIRTUAL_NUM; j++) {
				nodes.put(hash(getHash("SHARD-" + i + "-NODE-" + j), j),
						shardInfo);
			}
		}
	}

	public boolean add(String Node) {
		for (int i = 0, len = shards.size(); i < len; i++) {
			System.out.println("shards:" + shards.get(i));
			if (shards.get(i).equals(Node)) {
				return false;
			}
		}
		shards.add(Node);
		updateShardInfo();
		return true;
	}

	public boolean del(String Node) {

		for (int i = 0, len = shards.size(); i < len; i++) {
			System.out.println("shards:" + shards.get(i));
			if (shards.get(i).equals(Node)) {
				shards.remove(i);
				updateShardInfo();
				return true;
			}
		}
		return false;
	}

	public static void main(String[] args) {

		System.out.println(Hashing.md5().hashString("admin"));

		System.out.println(Hashing.murmur3_32().hashString("admin"));

		Random ran = new Random();
		ConsistencyHash Lbs = new ConsistencyHash(4);
		// hash.init();
		// hash.printMap();
		Lbs.add("192.168.0.1");
		Lbs.printMap();
		Lbs.add("192.168.0.2");
		Lbs.printMap();
		Lbs.add("192.168.0.3");
		Lbs.printMap();
		Lbs.add("192.168.0.4");
		Lbs.printMap();
		Lbs.add("192.168.0.4");
		Lbs.printMap();
		// Lbs.del("192.168.0.2");
		// Lbs.printMap();
		// ѭ��50�Σ���Ϊ��ȡ50����������Ч��ȻҲ�����������κε����������
		HashMap<Object, Integer> CC = new HashMap<Object, Integer>();
		int j = 0;
		for (int i = 0; i < 50; i++) {
			try {
				j = CC.get(Lbs.getShardInfo(Lbs.hash(
						Lbs.getHash(String.valueOf(i)),
						ran.nextInt(Lbs.VIRTUAL_NUM))));

			} catch (NullPointerException e) {

			} finally {
				j++;
				CC.put(Lbs.getShardInfo(Lbs.hash(
						Lbs.getHash(String.valueOf(i)),
						ran.nextInt(Lbs.VIRTUAL_NUM))), j);
			}
		}
		Iterator<Entry<Object, Integer>> iter = CC.entrySet().iterator();
		while (iter.hasNext()) {
			Map.Entry entry =  iter.next();
			Object key = entry.getKey();
			Object val = entry.getValue();
			System.out.println("key:" + key + "val:" + entry.getValue());

		}

	}

}
